package 牛客网_N.动态规划.gray_code_7;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;



/**
 * 格雷码
 * @author xuliyun
 * @summary
 * 后一个数为前一个数加上0，顺序遍历，然后加上1，倒序遍历
 */
public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int n = Integer.parseInt(in.nextLine());
		System.out.println(grayCode(n));
	}
	
    public static ArrayList<Integer> grayCode(int n) {
		HashMap<Integer, List<String>> map = new HashMap<Integer, List<String>>();
		List<String> list = new ArrayList<String>();
        List<String> list0 = new ArrayList<String>();
        list0.add("0");
		list.add("0");
		list.add("1");
		map.put(1, list);
        if(n == 0){
            return toInteger(list0);
        }
		if(n == 1){
			return toInteger(list);
		}
		
		for(int i = 1; i < n; i++){
			List<String> list2 = new ArrayList<String>();
			for(int j = 0; j < map.get(i).size(); j++){
				list2.add("0" + map.get(i).get(j));
			}
			for(int k = map.get(i).size()-1; k >= 0; k--){
				list2.add("1" + map.get(i).get(k));
			}
			map.put(i+1, list2);
		}
		return toInteger(map.get(n));
	}
	
	public static ArrayList<Integer> toInteger(List<String> list){
		ArrayList<Integer> list2 = new ArrayList<Integer>();
		for(String str : list){
			char[] dataStr = str.toCharArray();
			int num = 0;
			for(int i = 0; i < dataStr.length; i++){
				num += Math.pow(2, dataStr.length-1-i)*Integer.parseInt(Character.toString(dataStr[i]));
			}
			list2.add(num);
		}
		return list2;
	}
}
